Skip to main content

​
FNP - Protocol - Insert Operation Complete Flow

​
Summary (Explain Like I’m 5)

When you type a character in a collaborative encrypted document, here’s what happens invisibly behind the scenes:
  1. Your computer generates a secret position for the character using LSEQ
  2. Your computer encrypts the character with Kyber
  3. Your computer creates a mathematical proof proving “this is legit”
  4. Your computer sends all encrypted data to the server
  5. Server verifies the proof (can’t read your character!)
  6. Server places character in correct position using M²-ORE comparison
  7. Other computers receive the encrypted character and decrypt if they can
The entire process takes ~50 milliseconds on modern devices.

​
Technical Deep Dive

Insert Operation Protocol Flow (Complete): 
Replica A (Client) - Insert Phase:
  1. Generate LSEQ Position:
     - Request insertion between left_id and right_id
     - Plaintext: LSEQ.allocate(left_id, right_id) → new_id
     - Example: new_id = [⟨500, site=1, counter=5⟩]

  2. Encrypt Position (M²-ORE):
     - encrypted_id = M2ORE.Enc(pk_m2ore, new_id)
     - Deterministic (same randomness for consistency)

  3. Encrypt Content (Kyber):
     - Generate shared secret: (ss, ct) = Kyber.Encaps(pk_kyber)
     - Encrypt character: ciphertext = AES-256(ss, "H")
     - Result: (ct, ciphertext) - ciphertext only readable by you

  4. Generate Zero-Knowledge Proof:
     - Witness: {new_id, ss, your_signature}
     - Public Input: {encrypted_id, ct, ciphertext, timestamp}
     - Circuit: InsertProofCircuit (51,350 constraints)
     - Proof: π_insert ← Halo2.prove()

  5. Sign Operation:
     - op_bytes = serialize(INSERT, encrypted_id, ct, ciphertext, π_insert)
     - signature ← Dilithium.Sign(sk_dilithium, op_bytes)

  6. Broadcast to Server:
     - Operation {
         type: INSERT,
         char_id: encrypted_id,
         kyber_ct: ct,
         content: ciphertext,
         halo2_proof: π_insert,
         signature: signature,
         replica_id: 1,
         lamport_clock: 5,
         timestamp: 1730125600.234
       }

Server - Merge Phase:
  1. Receive Operation:
     - Validate format (all fields present)
     - Verify signature (Dilithium) - proves operation is authentic

  2. Verify Halo2 Proof (Blind):
     - Verify π_insert without accessing secret keys
     - Verify circuit constraints at random point ζ
     - Check: proof is valid probabilistically

  3. Verify LSEQ Constraints:
     - Check: new_id is in valid gap between neighbors
     - Check: Lamport clock increment is valid

  4. Determine Position via M²-ORE Comparison:
     - For each existing character pos_i:
       - Compare(encrypted_id, encrypted_pos_i)
       - If encrypted_id > encrypted_pos_i: new character goes after pos_i
     - Deterministic ordering using M²-ORE

  5. Merge into Document:
     - Insert into sorted list at computed position
     - Update metadata: {visible: true, author: replica_1, timestamp}
     - Increment document version

  6. Broadcast to Other Replicas:
     - Send Operation to all other connected clients
     - Each client verifies Halo2 proof
     - Each client applies CRDT semantics locally
     - Only clients with Kyber_sk[author] can decrypt content

Replica B (Other Client) - Receive Phase:
  1. Receive Operation from Server

  2. Verify Halo2 Proof:
     - Same verification as server (blind, no secrets needed)

  3. Decrypt Position (if authorized):
     - If you have M2ORE_sk[replica_1]: decrypt_id = M2ORE.Dec(sk_m2ore, encrypted_id)
     - Otherwise: can't decrypt but can still order using comparison

  4. Decrypt Content (if authorized):
     - If you have Kyber_sk[replica_1]:
       - ss = Kyber.Decaps(sk_kyber, ct)
       - character = AES-256.Dec(ss, ciphertext)
     - Otherwise: see encrypted content (privacy preserved!)

  5. Apply CRDT Semantics:
     - Insert character at position determined by M²-ORE ordering
     - Update local document state
     - Render to user: document now shows new character

​
Mermaid Diagrams

​
Key Terms

  • Blind Verification → Server verifies Halo2 proof without accessing secret keys
  • Lamport Clock → Monotonic counter ensuring causal ordering of operations
  • Deterministic Merge → M²-ORE comparison gives consistent ordering on server
  • Replicated State → Each client and server maintain copy of encrypted document
  • CRDT Semantics → Commutative, associative merge enables offline edits
  • Proof of Correctness → Halo2 ensures position and authorization are valid
  • Content Confidentiality → Only authorized users can decrypt with Kyber_sk
  • Non-repudiation → Dilithium signature proves operation originates from specific replica

​
Q/A

Q: Why does server need blind proof verification if it’s trusted? A: Server is trusted to coordinate but not trusted with plaintext. Blind proof verification ensures server can’t be compromised to read document content. Proofs verify correctness without needing access to secrets. Q: What if two clients insert at same position simultaneously? A: Both generate unique LSEQ identifiers (with different replica IDs and Lamport clocks). Server receives both operations. M²-ORE.compare() deterministically orders them. Both inserts are merged, neither lost. Q: Can the server reorder operations? A: No. Lamport clocks and timestamps provide causal ordering. If server reorders op1 and op2 where op1 happened first (lower Lamport clock), clients detect the inconsistency. Reordering would require forging new Halo2 proofs (cryptographically hard). Q: What’s the latency end-to-end? A: Typical: ~50ms. Breakdown: (1) Local proof generation: 1-2ms, (2) Network round-trip: 20-30ms, (3) Server verification: 5ms, (4) Broadcast to others: 10-20ms. Mobile WASM: slower but still <500ms acceptable. Q: Can I decrypt other users’ content? A: No. Each user’s content is encrypted with their Kyber public key. Other users see the Kyber ciphertext but can’t decrypt without your Kyber secret key. Server never has your secret key. Q: What happens if Halo2 proof verification fails? A: Server rejects the operation immediately. Operation is not merged, not broadcast, not visible to any client. Client receives rejection message; typically due to: invalid operation, corrupted proof, or replay attack.

​
Example / Analogy

Bank Check Analogy: When you insert character (type “H”), it’s like writing a bank check:
  1. You write the check:
    • Amount (position): Sealed in M²-ORE envelope
    • Payee (content): Sealed in Kyber envelope
    • Signature (Dilithium): Your autograph
    • Proof of funds (Halo2): Bank’s auditor verifies without seeing amount
  2. Bank processes check:
    • Verifies your signature (Dilithium)
    • Verifies auditor’s proof (Halo2 - bank can’t read amount!)
    • Determines position by comparing sealed envelopes (M²-ORE)
    • Merges with other checks
  3. Other customers see the check:
    • See that check exists (encrypted)
    • See it’s from you (signature)
    • If they have your envelope key: can read the amount
    • If not: see only encrypted data (privacy preserved!)
Cross-References: System Overview, M²-ORE Encryption, LSEQ CRDT, Kyber-1024, Halo2 Circuits Category: Protocol | Data Flow | Operations | Implementation Difficulty: Advanced ⭐⭐⭐⭐ Updated: 2025-11-28